package com.atguigu;

import java.util.Arrays;

/**
 * 迷宫问题测试
 *
 * @Author 剧情再美终是戏
 * @Date 2019/12/23
 * @return
 * @Version 1.0
 **/

// TODO 选择最优的线路
public class MazeTest {

    public static void main(String[] args) {

        // 新建一个迷宫
        int[][] maps = new int[5][5];

        // 设置迷宫上下的墙
        for (int i = 0; i < maps.length - 1; i++) {
            maps[0][i] = 1;
            maps[maps.length - 1][i] = 1;
        }

        // 设置迷宫左右的墙
        for (int i = 0; i < maps.length; i++) {
            maps[i][0] = 1;
            maps[i][maps.length - 1] = 1;
        }

        // 添加其他的挡板
        maps[3][2] = 1;
//        maps[4][2] = 1;
//        maps[5][2] = 1;
//        maps[6][2] = 1;
//        maps[7][2] = 1;
//        maps[8][2] = 1;

        // 输出迷宫图
        System.out.println("--------------------------迷宫图");
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps.length; j++) {
                System.out.print(maps[i][j] + " ");
            }
            System.out.println();
        }

        // 开始走迷宫
        doMaze(maps, 1, 1);

        // 走完迷宫输出的地图
        System.out.println("--------------------------走过的迷宫图");
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps.length; j++) {
                System.out.print(maps[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 走迷宫<br/>
     * <p>
     * 数字代表的意义:<br/>
     * 1==》墙<br/>
     * 2==》可以走通的路<br/>
     * 3==》走过的路，但不通<br/>
     * <p>
     * 规则：<br/>
     * 1、从i j下标开始<br/>
     * 2、到了[maps.length - 2][maps.length - 2]就算走通<br/>
     * 3、遵循这样的规则，下-->右-->上-->左<br/>
     *
     * @param maps
     * @param i    开始的下标1
     * @param j    开始的下标2
     * @return boolean 是否走通了
     * @Author 剧情再美终是戏
     * @Date 2019/12/23
     * @Version 1.0
     **/

    public static boolean doMaze(int[][] maps, int i, int j) {
        if (maps[maps.length - 2][maps.length - 2] == 2) {
            return true;
        } else {
            // 要走没有走过的路，为0就是没有走过的
            if (maps[i][j] == 0) {
                // 假设这个节点是可以走得通的
                maps[i][j] = 2;

                // 探路
                if (doMaze(maps, i + 1, j)) { // 向下
                    return true;
                } else if (doMaze(maps, i, j + 1)) { // 向右
                    return true;
                } else if (doMaze(maps, i - 1, j)) { // 向上
                    return true;
                } else if (doMaze(maps, i, j - 1)) { // 向左
                    return true;
                } else {
                    maps[i][j] = 3; // 将节点设置为3，表示已经走过，代表不通IN
                    return false;
                }
            } else {
                return false;
            }
        }
    }
}
